/**
 * @a http://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/
 */

#include "../../common.h"
#include <vector>
#include <queue>
#include <utility>

using namespace std;

class Solution {
    // 定义方向数组，设为静态常量更清晰
    static const int dx[4];
    static const int dy[4];

public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size();
        int n = maze[0].size();

        // 1. 将队列和 visited 数组作为局部变量
        queue<pair<int, int>> que;
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        // 2. 将入口点加入队列，并标记为已访问
        que.push({entrance[0], entrance[1]});
        visited[entrance[0]][entrance[1]] = true;

        int steps = 0; // 用来记录步数

        // 3. 开始 BFS
        while (!que.empty()) {
            steps++; // 向外探索一层，步数加 1
            int level_size = que.size(); // 当前层级的节点数

            for (int i = 0; i < level_size; ++i) {
                auto [curr_r, curr_c] = que.front();
                que.pop();

                // 4. 探索四个方向
                for (int j = 0; j < 4; ++j) {
                    int next_r = curr_r + dx[j];
                    int next_c = curr_c + dy[j];

                    // 检查新位置是否合法：在边界内、不是墙、未被访问过
                    if (next_r >= 0 && next_r < m && next_c >= 0 && next_c < n &&
                        maze[next_r][next_c] == '.' && !visited[next_r][next_c]) {
                        
                        // 5. 检查是否是出口
                        // 出口定义：边界上的空格子。入口本身不算出口。
                        // 因为我们从入口开始，steps 从 1 开始计数，所以找到的第一个边界点必然不是入口本身。
                        if (next_r == 0 || next_r == m - 1 || next_c == 0 || next_c == n - 1) {
                            return steps; // 找到了最近的出口，返回步数
                        }

                        // 6. 如果不是出口，则加入队列，继续探索
                        que.push({next_r, next_c});
                        visited[next_r][next_c] = true;
                    }
                }
            }
        }

        // 7. 如果队列为空还没找到出口，说明没有通路
        return -1;
    }
};

// 在类外初始化静态成员变量
const int Solution::dx[4] = {0, 0, 1, -1};
const int Solution::dy[4] = {1, -1, 0, 0};